package teach.sort;

import java.util.Arrays;

public class QuickSort1 {
    public static void main(String[] args) {
        int[] arr = {8, 1, 4, 9, 0, 3, 5, 2, 7, 6};
        System.out.println(Arrays.toString(arr));
        sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr,int start,int end){
        if(start>=end){
            return;
        }
        int pivot = arr[end];
        int x = start-1;
        for(int i=start;i<end;i++){
            if(arr[i]<=pivot){
                if(i-x>1){
                   int temp = arr[i];
                   arr[i] = arr[x+1];
                   arr[x+1] = temp;
                }
                x++;
            }
        }
        //System.arraycopy(arr,x+1,arr,x+2,end-x-1);
        arr[end] = arr[x+1];
        arr[x+1] = pivot;

        sort(arr,start,x);
        sort(arr,x+2,end);
    }
}
